The invention relates generally to transportation networks, and relates more particularly to the incorporation of dynamic data in transportation network calculations.
FIG. 1 is a schematic diagram illustrating a typical large-area transportation network 100. The transportation network 100 comprises a plurality of urban metropolitan areas 1021-102N (hereinafter collectively referred to as “metropolitan areas 102), towns 1041-104N (hereinafter collectively referred to as “towns 104”) and inter-urban and/or rural areas (generally designated 106) situated between the metropolitan areas 102 and towns 104. The metropolitan areas 102, towns 104 and inter-urban/rural areas 106 that comprise the transportation network 100 may span a large geographical area (e.g., comprising a plurality of cities, states, regions or countries).
When traveling between locations in a transportation network, it is typically desirable to identify a shortest path, or best (e.g., fastest) route, to travel from an origin to a destination. Conventional applications such as internet mapping and vehicle navigation systems typically compute this best route based on static, non-state-dependent data about links in the transportation network (e.g., speed limits, numbers of lanes, average loads).
A problem with this approach is that dynamic, state-dependent data that may influence travel time (e.g., current traffic conditions or other environmental factors) is not accounted for. Thus, a computed route may not, in fact, be the best route at a given time. Although some methods currently exist that do account for current traffic states, these existing methods are computationally intensive and limited to small or moderately-sized geographic areas. Moreover, these methods do not function well where access to real-time data is limited to only some roads in the transportation network (e.g., as with large urban transportation networks).
Thus, there is a need for a method and apparatus for estimating travel times over a transportation network based on limited real-time data.